#include <stdio.h>/*该文件包含pringtf()等函数*/
#include <stdlib.h>/*该文件包含exit()等函数*/
#include <malloc.h>/*该文件包含malloc()等函数*/

#define STACK_MAX_SIZE 100 // 栈最多支持存放100个数据元素

#define bool int
// 要求将所有代码写在本文件内
// 必须实现下列函数。可以自行增加别的函数。
// 请勿修改由老师所提供的main.h文件的内容。

/*算符间的优先关系表(+,-,*,/,(,),#)*/
char cpri[7][7]={
        {'>','>','<','<','<','>','>' },
        {'>','>','<','<','<','>','>' },
        {'>','>','>','>','<','>','>' },
        {'>','>','>','>','<','>','>' },
        {'<','<','<','<','<','=',' '},
        {'>','>','>','>',' ','>','>'},
        {'<','<','<','<','<',' ','='}
};

/*定义栈的函数*/
typedef struct stack
{
    int * base;
    int * top;
    int number_of_elements; // 栈内实际数据元素个数
} * Stack;

// 初始化名为s的栈，初始化成功，返回0，否则返回1。
int init_stack(Stack * s){
    (*s) = (Stack )malloc(sizeof(Stack));
    (*s)->base = (int *)malloc(STACK_MAX_SIZE * sizeof(int));
    if(!(*s)->base)
        return 1;  //存储分配失败，返回error
    (*s)->top = (*s)->base;  //分配成功则让栈顶指针指向栈底指针
    (*s)->number_of_elements = STACK_MAX_SIZE;
    return 0;
}

// 只返回栈顶元素，通过result变量返回栈顶元素的值。函数返回值用于表示执行状态：0，成功；1，不成功。
int get_top(Stack s, char * symbol)
{
    //int result;
    if(s->top == s->base)
    {
        return 1;
    }
    (*symbol) = *(s->top);
    return 0;
}

// 入栈。返回值表示是否压栈成功：0，成功；1，不成功。
int push(Stack s, char operator_or_operand)
{
    if(s->top - s->base >= s->number_of_elements){
        return 1;
    }
    *(++s->top) = operator_or_operand;
    return 0;
}

int pop(Stack s, char * p_operator_or_operand)

{
    if(s->top == s->base) {//判断是否栈空
        return 0;
    }
    *p_operator_or_operand = *(s->top);
    s->top--;
    return 1;
}

// 判断刚扫描到的symbol是否操作符。如果symbol是操作符，返回1，否则返回0。
int is_optr(char symbol)
{
    switch(symbol){
        case '+':
        case '-':
        case '*':
        case '/':
        case '(':
        case ')':
        case '#':
            return 1;
        default: return 0;
    }
}

/*返回运算符在数组中的索引*/
int demo(char c)
{
    int in;
    switch(c){
        case '+': in = 0;break;
        case '-': in = 1;break;
        case '*': in = 2;break;
        case '/': in = 3;break;
        case '(': in = 4;break;
        case ')': in = 5;break;
        case '#': in = 6;break;
        default: return -1;
    }
    return in;
}

/*运算符优先级的判定*/
char precede(char top,char c)
{
    int i,j;
    i=demo(top);
    j=demo(c);
    return cpri[i][j];
}

//运算函数
char operate(char a,char theta,char b)
{
    int a1,b1;
    char result=0;
    a1 = a - '0';
    b1 = b - '0';

    switch(theta)
    {
        case '+':
            result = (char)((a1+b1)+'0');
            break;
        case '-':
            result = (char)((a1-b1)+'0');
            break;
        case '*':
            result = (char)((a1*b1)+'0');
            break;
        case '/':
            result = (char)((a1/b1)+'0');
            break;
    }
    return result;
}


// 判断刚扫描到的symbol是否操作符。如果symbol是操作符，返回1，否则返回0。
bool is_operator(char symbol)
{
    if(symbol == '+' || symbol == '-' ||symbol == '*' ||symbol == '/' ||
       symbol == '(' ||symbol == ')' ||symbol == '#'){
        return 1;
    }
    return 0;
}

// 判断刚扫描到的symbol是否操作数。如果symbol是操作数，返回1，否则返回0。
bool is_operand(char symbol){
    if(symbol >= '1'&& symbol <= '9' ){
        return 1;
    }
    return 0;
}

// 用于计算表达式的值，比如#3*(2+6)/4#。
// 返回值表示求值状态：0，合法表达式，成功求值；1，表达式不合法。
// result变量用于返回计算结果。
int evaluate(char * expression, int * result)
{
    int k = 1;
    char c=0,theta=0;
    char e=1;
    char a=0,b=0;
    Stack OPND;
    Stack OPTR;
    init_stack(&OPTR);
    init_stack(&OPND);
    c = expression[k];
    k++;
    push(OPTR,expression[0]);
    while( expression[k]!= '#' ||e!='#'){
        if(is_operand(c)){
            push(OPND,c);
            c = expression[k]; //读取下一字符c = '#'
            if(c != '#'){
                k++;
            }
        }
        if(is_operator(c)){
            get_top(OPTR,&e);
            switch(precede(e,c))
            {
                case '<':
                    push(OPTR,c);
                    c = expression[k];//栈顶元素的优先权低//c = '2'
                    if(c != '#'){
                        k++;//expression[k]=='#'
                        get_top(OPTR,&e);
                    }
                    break;
                case '=': //脱括号并接受下一字符
                    pop(OPTR,&c);
                    c = expression[k];//c = *
                    k++;//expression[k]=='2'
                    break;
                case '>': //退栈并将运算结果入
                    pop(OPTR,(char*)&theta);
                    pop(OPND,(char*)&b);
                    pop(OPND,(char*)&a);
                    push(OPND,operate(a,theta,b));
                    get_top(OPTR,&e);
                    break;
            }
        } else{
            return 1;
        }
    }
    get_top(OPND,&e);
    *result =  e - '0';
    return *result;
}

int main()
{
    char *symbol = "#3*(2+6)/4#";
    int result=0;
    evaluate(symbol,&result);
    printf("%d",result);
    system("pause");

}
